Technical Field
The present invention relates to information protection and queues and, more particularly, to methods for single-owner multi-consumer work queues for repeatable tasks.
Description of the Related Art
Single-owner multi-consumer work queues, also commonly referred to as work stealing queues, are typically used to hold the work created by a thread, while allowing other threads to steal work if their own work queues are empty. Since a work queue may be accessed concurrently by the queue's owner and other threads attempting to steal work, synchronization is needed. In particular, the thread's owner is required to use “special” atomic instructions (e.g., compare-and-swap instructions, also interchangeably referred to herein by the acronym “CAS”), which are typically significantly slower than regular instructions.
In general, each task in the work queue should be extracted exactly once from the queue (and hence performed exactly once, e.g., transfer money). However, in many other cases (e.g., perform a calculation), it is acceptable for tasks to be performed one or more times, i.e., when tasks are idempotent. For such latter class of tasks (i.e., those tasks to be performed one or more times), this should be an opportunity to design work stealing queues that guarantee correct concurrent access with less synchronization overheads than work stealing queues that guarantee that each task is extracted exactly once.